package com.example.Arithmetic.Arithmetic;

import java.util.Arrays;

/**
 * 日期：2024/1/1
 * 时间：15:00
 * 描述：求最长相同字符串，动态规划求解
 */
public class LCSubstring {
    static void print(int[][] dp, String a, String b) {
        System.out.println("-".repeat(23));
        Object[] array = a.chars().mapToObj(i -> String.valueOf((char) i)).toArray();
        System.out.printf("  " + "%2s ".repeat(a.length()) + "%n", array);
        for (int i = 0; i < b.length(); i++) {
            int[] d = dp[i];
            array = Arrays.stream(d).boxed().toArray();
            System.out.printf(b.charAt(i) + " " + "%2d ".repeat(d.length) + "%n", array);
        }
    }
    /*
            i   t   h   e   i   m   a
         t  0   1   0   0   0   0   0
         h  0   0   2   0   0   0   0
         e  0   0   0   3   0   0   0
         n  0   0   0   0   0   0   0
     */

    public static void main(String[] args) {
        System.out.println(lcs("itheima", "theimallll"));
    }

    private static int lcs(String a, String b) {
        int[][] str = new int[b.length()][a.length()];
        int max = 0;
        for (int i = 0; i < b.length(); i++) {
            for (int j = 0; j < a.length(); j++) {
                if (a.charAt(j) == b.charAt(i)) {
                    if (i == 0 || j == 0) {
                        str[i][j] = 1;
                    } else {
                        str[i][j] = str[i - 1][j - 1] + 1;
                    }
                    max = Math.max(str[i][j], max);
                }
            }
            print(str,a,b);
        }
        return max;
    }
}
